package com.mc.knn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class KNN {

	/**
	 * KNN分类
	 * @param tar 目标向量
	 * @param data 训练数据
	 * @param labels 训练数据标识
	 * @param k 参数K
	 * @return 分类类别
	 */
	public static int classify(double[] tar,double[][] data,int[] labels,int k){
		if(data.length!=labels.length||tar.length!=data[0].length)return -1;
		
		class Result{
			double dist;
			int label;
			public Result(double dist,int label){
				this.dist = dist;
				this.label = label;
			}
		}
		List<Result> list = new ArrayList<Result>();
		//计算目标数据到训练数据的距离
		for(int i=0;i<data.length;i++){
			double tempResult=0;
			for(int j=0;j<data[0].length;j++){
				tempResult+=Math.pow((data[i][j]-tar[j]), 2);
			}
			list.add(new Result(tempResult,labels[i]));
		}
		
		//对计算结果按照距离升序排序
		Collections.sort(list, new Comparator<Result>(){
			public int compare(Result o1,Result o2){
				if(o1.dist-o2.dist<0)
					return -1;
				else if(o1.dist-o2.dist==0)
					return 0;
				return 1;
			}
		});
		//根据参数k取前k个数据进行统计，占比最高的类别为目标类别
		Result[] array = list.toArray(new Result[0]);
		array = Arrays.copyOf(array, k);
		//键为类别，值为该类别的计数
		HashMap<Integer,Integer> cate = new HashMap<Integer,Integer>();
		for(int i=0;i<array.length;i++){
			if(cate.containsKey(array[i].label))
				cate.put(array[i].label, cate.get(array[i].label)+1);
			else
				cate.put(array[i].label, 1);
		}
		//获取最大的计数结果所对应的类别作为结果
		Set<Map.Entry<Integer,Integer>> entrySet = cate.entrySet();
		Iterator<Map.Entry<Integer,Integer>> iter = entrySet.iterator();
		int res=0;
		int lab=0;
		while(iter.hasNext()){
			Entry<Integer, Integer> entry = iter.next();
			if(entry.getValue()>res){
				res = entry.getValue();
				lab = entry.getKey();
			}
		}
		return lab;
	}
	
	
	
	public static void main(String[] args) {
		double[] tar = {1,2,3,4};
		double[][] data ={{1,1,1,1},{1,1,2,3},{3,4,5,6},{3,3,3,3}};
		int[] labels={1,1,2,2};
		System.out.println(KNN.classify(tar, data, labels,2));
	}
}
